package com.zp.self.module.level_4_算法练习.数据结构.链表;

/**
 * @author By ZengPeng
 */
public class 力扣_86_分隔链表 {
    //测试
    public static void main(String[] args) {

        ListNode node = ListNode.getNode();
        ListNode partition = new 力扣_86_分隔链表().partition(node, 0);
        while (partition!=null){
            System.out.print(partition.val+",");
            partition = partition.next;
        }
    }

    /**
    题目：给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，
        使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
        你应当 保留 两个分区中每个节点的初始相对位置。

     示例 1：
     输入：head = [1,4,3,2,5,2], x = 3
     输出：[1,2,2,4,3,5]

     示例 2：
     输入：head = [2,1], x = 2
     输出：[1,2]

    分析：【perfect】原来你叫虚拟头节点阿~
       1.创建两个虚拟头节点：分别记录前半部分、后半部分的起点
                创建两个不断变化的前节点、后节点;最后再拼接起来

    边界值 & 注意点：
       1.
     **/
    public ListNode partition(ListNode head, int x) {
        ListNode res = new ListNode(),pro=res;
        ListNode resAfter = new ListNode(),after = resAfter;
        while (head!=null){
            if(head.val<x){
                pro.next = head;
                pro=pro.next;
                head=head.next;
                pro.next=null;
            }else{
                after.next = head;
                after=after.next;
                head=head.next;
                after.next=null;
            }
        }
        if(res.next!=null){
            pro.next=resAfter.next;
            return res.next;
        }else
            return resAfter.next;
    }
}
